package com.cqs.leetcode.array;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SetMatrixZeroes73 {

    /**
     * 记录哪些行，哪些列出现了0
     * 然后按照记录结果进行改写
     * 时间复杂度O(M*N)
     * 空间复杂度O(M+N)
     */
    static class Solution {
        public void setZeroes(int[][] matrix) {
            Set<Integer> row = new HashSet<>();
            Set<Integer> cell = new HashSet<>();
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) {
                        row.add(i);
                        cell.add(j);
                    }
                }
            }
            for (Integer r : row) {
                for (int i = 0; i < matrix[0].length; i++) {
                    matrix[r][i] = 0;
                }
            }

            for (Integer c : cell) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][c] = 0;
                }
            }
//            for (int i = 0; i < matrix.length; i++) {
//                for (int j = 0; j < matrix[0].length; j++) {
//                    if (row.contains(i) || cell.contains(j)) matrix[i][j] = 0;
//                }
//            }
        }
    }

    static class Solution2 {
        public void setZeroes(int[][] matrix) {
            //先处理行
            int row = 0;

        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<int[][]> list = new ArrayList<>();
        list.add(new int[][]{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}});
        list.stream().forEach(it -> {
            System.out.print(it + "\t");
            solution.setZeroes(it);
            System.out.println(it);
        });
    }
}
